package _17_graph;

import java.util.Arrays;

/**
 * @author: mornd
 * @dateTime: 2023/6/26 - 11:52
 * 并查集合(不相交集合)， kruskal 算法使用到
 */
public class DisJoinSet {
    int[] s;
    int[] size; // union by size

    public DisJoinSet(int size) {
        s = new int[size];
        this.size = new int[size];
        for (int i = 0; i < size; i++) {
            s[i] = i;
        }
        Arrays.fill(this.size, 1);
    }

    // 找老大，下标与元素值相等即为老大
    public int find(int i) {
        if (i == s[i]) {
            return i;
        }
        return s[i] = find(s[i]);
    }

    //使两个顶点相交
    public void union(int i, int j) {
        if (size[i] < size[j]) {
            // j对应新老大索引，i对应新小弟索引
            s[i] = j;
            size[j] = size[i] + size[j];
        } else {
            // i对应新老大索引，j对应新小弟索引
            s[j] = i;
            size[i] = size[i] + size[j];
        }
    }
}
